import math
from typing import List, Tuple, Dict


class Chromosome:
    """表示无人机路径问题遗传算法中的染色体
    
    属性:
        sequence (List[int]): 访问点的顺序
        _valid_points (Tuple[int]): 所有有效点（包含起点和终点）
        _profits (List[int]): 各点的收益值（只读）
        _valid_matrix (List[List[int]]): 有效路径的邻接矩阵（只读）
        _time_limit (int): 最大允许时间（只读）
        _valid_time (int): 开始惩罚前的时间（只读）
        _penalty_interval (int): 惩罚计算的时间间隔（只读）
        _penalty_rate (int): 每个间隔的惩罚率（只读）
        total_cost (int): 路径总成本
        total_profit (int): 惩罚后的总收益
    """
    
    START_POINT = 0
    END_POINT = 1

    def __init__(
        self,
        sequence: List[int],
        valid_points: List[int],
        profits: List[int],
        valid_matrix: List[List[int]],
        time_limit: int,
        valid_time: int,
        penalty_interval: int,
        penalty_rate: int
    ) -> None:
        """初始化染色体实例

        参数:
            sequence: 访问点的顺序
            valid_points: 所有有效点（包含起点和终点）
            profits: 各点的收益值
            valid_matrix: 有效路径的邻接矩阵
            time_limit: 最大允许时间
            valid_time: 开始惩罚前的时间
            penalty_interval: 惩罚计算的时间间隔
            penalty_rate: 每个间隔的惩罚率
        """
        self._valid_points = tuple(valid_points)
        self._validate_sequence(sequence)
        
        self.sequence = sequence
        self._profits = tuple(profits)  # 转换为元组确保不可变
        self._valid_matrix = tuple(tuple(row) for row in valid_matrix)  # 转换为嵌套元组确保不可变
        self._time_limit = time_limit
        self._valid_time = valid_time
        self._penalty_interval = penalty_interval
        self._penalty_rate = penalty_rate
        
        self.total_cost = int(self._calculate_cost())
        self.total_profit = int(self._calculate_profit())
        
        self._normalize_sequence()


    def _validate_sequence(self, sequence: List[int]) -> None:
        """验证序列是否符合要求
        
        参数:
            sequence: 要验证的序列
            
        异常:
            AssertionError: 如果序列无效
        """
        assert sequence[0] == self.START_POINT, "Sequence must start with 0"
        assert self.END_POINT in sequence, "Sequence must contain 1"


    def _normalize_sequence(self) -> None:
        """Normalize sequence to ensure it starts at depot (0) and contains only valid points"""
        # Ensure sequence starts at depot
        if self.sequence[0] != 0:
            self.sequence.insert(0, 0)
            
        # Remove duplicates while preserving order
        seen = set()
        self.sequence = [x for x in self.sequence if not (x in seen or seen.add(x))]
        
        # Validate all points are in valid_points
        invalid_points = [p for p in self.sequence if p not in self._valid_points]
        assert not invalid_points, f"Sequence contains invalid points: {invalid_points}"


    def _calculate_profit(self) -> int:
        """计算从起点到终点的总收益
        
        返回:
            应用惩罚后的总收益
        """
        total = 0
            
        for i in range(len(self.sequence)-1):
            current = self.sequence[i]
            next_point = self.sequence[i+1]
            
            # 到达终点后停止累加收益
            if current == self.END_POINT:
                break
                
            # 只有当前点不是起点或终点时才累加收益
            if current not in [self.START_POINT, self.END_POINT]:
                total += int(self._profits[current])
     
        # 如果超时则应用惩罚
        if self.total_cost <= self._valid_time:
            over_time = max(0, self.total_cost - self._time_limit)
            penalty = math.ceil(over_time / self._penalty_interval) * self._penalty_rate
            total -= penalty
        else:
            total = 0
            
        return int(total)


    def _calculate_cost(self) -> int:
        """计算从起点到终点的总成本
        
        返回:
            路径的总成本
        """
        total = 0
        for i in range(len(self.sequence)-1):
            current = self.sequence[i]
            next_point = self.sequence[i+1]
            total += int(self._valid_matrix[current][next_point])
            if next_point == self.END_POINT:
                break
        return int(total)


    def get_path_nodes(self) -> List[int]:
        """获取终点之前的路径节点
        
        返回:
            包含终点在内的路径节点列表
        """
        end_idx = self.sequence.index(self.END_POINT)
        return self.sequence[:end_idx+1]


    def get_unvisited_nodes(self) -> List[int]:
        """获取路径中未访问的节点（终点之后）
        
        返回:
            终点之后序列中的节点列表
        """
        start_idx = self.sequence.index(self.END_POINT) + 1
        return self.sequence[start_idx:]


    def __str__(self) -> str:
        """染色体的字符串表示
        
        返回:
            格式化字符串，显示序列、收益和成本
        """
        return (f"Chromosome(sequence={self.sequence}, "
                f"total_profit={self.total_profit}, "
                f"total_cost={self.total_cost})")
